package com.zengqingfa.algorithm.cz.chapter02;

import java.util.Arrays;

/**
 * @author zengqingfa
 * @className ShellSort
 * @description 希尔排序 缩小增量排序
 * @create 2021/8/6 21:45
 */
public class ShellSort {

    public static void main(String[] args) {
        Integer[] arr = {9, 1, 2, 5, 7, 4, 8, 6, 3, 5};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(Comparable[] arr) {
        //确定增量
        int h = 1;
        while (h < arr.length / 2) {
            h = 2 * h + 1;
        }
        System.out.println("增量h:" + h);
        //当增量小于1时，退出排序
        while (h >= 1) {
            //从h处元素开始的元素，向前插入，找到待插入的元素的位置
            for (int i = h; i < arr.length; i++) {
                //a[i]就是待插入的元素
                // 把a[i]插入到a[i-h],a[i-2h],a[i-3h]...序列中
                for (int j = i; j >= h; j = j - h) {
                    if (greater(arr[j - h], arr[j])) {
                        swap(arr, j - h, j);
                    } else {
                        break;
                    }
                }
            }
            //递减增量h
            h = h / 2;
        }

    }

    /**
     * 判断a是否大于b
     *
     * @param a
     * @param b
     * @return
     */
    public static boolean greater(Comparable a, Comparable b) {
        return a.compareTo(b) > 0;
    }

    /**
     * 交换数组arr中索引i和j处的元素
     *
     * @param arr
     * @param i
     * @param j
     */
    public static void swap(Comparable[] arr, int i, int j) {
        Comparable temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}